class Solution:
    def findWords(self, board, words):
        head = {}
        r = set()
        for word in words:
            self.insert(head, word)
        for i in range(len(board)):
            for j in range(len(board[i])):
                r = r.union(self.helpFind(board, head, set(), i, j))

        return list(r)

    def helpFind(self, board, dic, pointHis, x, y):
        if (x, y) in pointHis:
            return set()
        if board[x][y] not in dic:
            return set()
        pointHis.add((x, y))
        allResult = set()
        if '$' in dic[board[x][y]]:
            allResult.add(board[x][y])
        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < len(board) and 0 <= j < len(board[0]):
                result = self.helpFind(board, dic[board[x][y]], pointHis, i, j)
                for r in result:
                    allResult.add(board[x][y] + r)
        pointHis.remove((x, y))
        return allResult

    def insert(self, head, word: str) -> None:
        tmp = head
        for i in word:
            if i in tmp:
                tmp = tmp[i]
            else:
                tmp[i] = {}
                tmp = tmp[i]
        tmp['$'] = True


if __name__ == '__main__':
    so = Solution()
    words = ["oath", "pea", "eat", "rain"]
    board = [
        ['o', 'a', 'a', 'n'],
        ['e', 't', 'a', 'e'],
        ['i', 'h', 'k', 'r'],
        ['i', 'f', 'l', 'v']
    ]

    r = so.findWords(board, words)
    print(r)
